package DP;

import java.util.*;

/**
 * @author dx
 * @version 1.0
 * @date 2022/5/17 9:47
 * @description:  力扣 17电话号码的组合
 */
public class LetterCombination {
    public static void main(String[] args) {
        Scanner sr = new Scanner(System.in);
        String digits = sr.nextLine();
        List<String> ans = new ArrayList<>();
        ans = new LetterCombination_Solution().letterCombinations(digits);
        for(String x:ans){
            System.out.print(x+" ");
        }
    }
}


class LetterCombination_Solution{
    List<String> res = new ArrayList<>();
    public List<String> letterCombinations(String digits) {

        if(digits.length() == 0){
            return res;
        }
        Map<Character,String> str = new HashMap<>();
        str.put('2',"abc");
        str.put('3',"def");
        str.put('4',"ghi");
        str.put('5',"jkl");
        str.put('6',"mno");
        str.put('7',"pqrs");
        str.put('8',"tuv");
        str.put('9',"wxyz");
        int index = 0;
        StringBuffer trace = new StringBuffer();
        backtrace(res,trace,index,digits,str);
        return res;

    }

    public void backtrace(List<String> res,StringBuffer trace,int index,String digits,Map<Character,String> str){

        if(index == digits.length()){
            res.add(trace.toString());
            return;
        }

        String  x = str.get(digits.charAt(index));
        for(int i = 0;i < x.length();i++){
            trace.append(x.charAt(i));
            backtrace(res,trace,index+1,digits,str);
            trace.deleteCharAt(index);
        }
    }

}